home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / lang / c-part1 / 6620 < prev    next >
Encoding:
Text File  |  1996-08-05  |  1.3 KB  |  33 lines
  1. Newsgroups: comp.lang.c
  2. Path: howland.reston.ans.net!psinntp!psinntp!psinntp!psinntp!wmi2!joel
  3. From: joel@wmi.com (Joel Coltoff)
  4. Subject: Re: Fastest way to computer log(base2) of x?
  5. Message-ID: <1996Feb7.205235.29897@wmi.com>
  6. Organization: Woodward McCoach, Inc.
  7. References: <4f647p$lc5@druid.borland.com> <9602061633.AA15316@dxmint.cern.ch> <4f8rtu$1ib@fountain.mindlink.net>
  8. Date: Wed, 7 Feb 1996 20:52:35 GMT
  9.  
  10.  
  11. In a project I worked on a LONG time ago we solved this in a
  12. clever way. We had the one advantage that there was an upper
  13. bound on x.  We needed to find y such that 2**y >= x for values
  14. of x <= 65535 ( i.e y <= 16).
  15.  
  16. The approach we took was a binary search using the "? :" construct.
  17. It works out to a few simple compares and no shifts, multiplies, etc.
  18.  
  19. I don't have it at hand and can't be bothered to reconstruct it. It
  20. shouldn't take long for you to do. The general scheme was (I don't
  21. claim that this form of it is right)
  22.  
  23.     y = x < 512 ?
  24.         ( x < 32 ?
  25.         ( x < 8 ?
  26.         ( x < 4 ? ( x < 2 ? : 1 ) : 2 ) : 3 )) :  x < 128 ? :
  27.                                       ^     ^     ^
  28.                                       |     |     |
  29.  values for y -------------------------------------
  30.  
  31. Yes it's an unreadable mess but it is fast. For more fun take the parens
  32. out after you've got it working.
  33.